// 二叉排序树
#include "BinarySortTree.h"
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0

BTNode *CreateTreeNode(ElementType element)
{
    BTNode *treeNode=(BTNode *)malloc(sizeof(BTNode));
    if(treeNode==NULL)
    {
        printf("treeNode malloc error!\n");
        return NULL;
    }
    treeNode->data=element;
    treeNode->left=NULL;
    treeNode->right=NULL;
    treeNode->parent=NULL;
    return treeNode;
}

int InitLBTree(LBTree *tree,ElementType element)
{
    tree->root=CreateTreeNode(element);
    if(tree->root==NULL)
    {
        printf("InitLBTree create error!\n");
        return false;
    }
    else
    {
        return true;
    }
    return 0;
}

void Insert(BTNode *node,ElementType element)
{
    if(node==NULL)
        return;
    if(node->left==NULL && element<node->data)
    {
        node->left=CreateTreeNode(element);
        node->left->parent=node;
        return;
    }

    if(node->right==NULL && element>node->data)
    {
        node->right=CreateTreeNode(element);
        node->right->parent=node;
        return;
    }

    if(element<node->data)
    {
        Insert(node->left,element);
    }
    else
    {
        Insert(node->right,element);
    }
}
void InsertNode(LBTree *tree, ElementType element)
{
    Insert(tree->root,element);
}

void MidPrint(BTNode *node)
{
    if(node!=NULL)
    {
        MidPrint(node->left);
        printf("%d ",node->data);
        MidPrint(node->right);
    }
}
void MidTravel(LBTree *tree)
{
    MidPrint(tree->root);
    printf("\n");
}

void PrevPrint(BTNode *node)
{
    if(node!=NULL)
    {
        printf("%d ",node->data);
        PrevPrint(node->left);       
        PrevPrint(node->right);
    }
}
void PrevTravel(LBTree *tree)
{
    PrevPrint(tree->root);
    printf("\n");
}

void PostPrint(BTNode *node)
{
    if(node!=NULL)
    {        
        PostPrint(node->left);       
        PostPrint(node->right);
        printf("%d ",node->data);
    }
}
void PostTravel(LBTree *tree)
{
    PostPrint(tree->root);
    printf("\n");
}

void FreeNode(BTNode *node)
{
    if(node==NULL)
        return;    
    FreeNode(node->left);
    FreeNode(node->right);
    FreeNode(node);
}
void FreeTree(LBTree *tree)
{
    FreeNode(tree->root);
    tree->root=NULL;
}

BTNode *SearchNode(BTNode *node,ElementType element)
{
    if(node==NULL)
        return NULL;
    if(node->data==element)
        return node;
    else if(node->data<element)
    {
        return SearchNode(node->right,element);
    }
    else 
    {
        return SearchNode(node->left,element);
    }
}
BTNode *SearchElement(LBTree *tree,ElementType element)
{
    return SearchNode(tree->root,element);
}

void DeleteElement(LBTree *tree, ElementType element)
{
    BTNode *targetNode = SearchNode(tree->root,element);
    if(targetNode == NULL)
        return;
    if(targetNode->left ==NULL && targetNode->right == NULL)
    {
        if(targetNode->parent->left == targetNode)
        {
            targetNode->parent->left = NULL;
        }
        else
        {
            targetNode->parent->right = NULL;
        }
        free(targetNode);
    }
    else if(targetNode->right == NULL)
    {
        if(targetNode->parent==NULL)
        {
            tree->root=targetNode->left;
        }
        else if(targetNode->parent->left == targetNode)
        {
            targetNode->left->parent = targetNode->parent;
            targetNode->parent->left = targetNode->left;
        }
        else
        {
            targetNode->left->parent = targetNode->parent;
            targetNode->parent->right = targetNode->left;
        }
        free(targetNode);
    }
    else if(targetNode->left == NULL)
    {
        if(targetNode->parent==NULL)
        {
            tree->root=targetNode->right;
        }
        
        else if(targetNode->parent->right == targetNode)
        {
            targetNode->right->parent = targetNode->parent;
            targetNode->parent->right = targetNode->right;
        }
        else
        {
            targetNode->right->parent = targetNode->parent;
            targetNode->parent->left = targetNode->right;
        }
        free(targetNode);
    }
    else if(targetNode->left != NULL && targetNode->right != NULL)
    {
        BTNode *MinNode = targetNode->right;
        while(MinNode->left != NULL)
        {   
            MinNode = MinNode->left;
        }
        targetNode->data = MinNode->data;

        if(MinNode->parent != targetNode)
        {
            MinNode->parent->left = MinNode->right;         
        }
        else
        {
            targetNode->right = MinNode->right;
        }
        free(MinNode);
    }
}